// // 16、已知一个带有表头结点的单链表，结点结构为：
// //   =============================
// //   |      data      link       |
// //   =============================
// // 假设该链表只给出了头指针 list。
// // 在不改变链表的前提下，请设计一个尽可能高效的算法，
// // 查找链表中 倒数第 k 个位置上的结点( k 为正整数)。
// // 若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只 返回 0。
// //
// // 要求：
// // （1）描述算法的基本设计思想；
// // （2）描述算法的详细实现步骤；
// // （3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++语言实现），关键之处请给出简要注释。
// #include <stdio.h>
// #include <stdlib.h>
// #include "windows.h"
// #include <assert.h>
// typedef int ElemType;
// //节点结构
// typedef struct LinkNode {
//     ElemType data;
//     struct LinkNode* next;
// }LinkNode;
// //链表结构
// typedef struct LinkList {
//     LinkNode* head;
// }LinkList;
// //链表初始化
// LinkList* LinkInit() {
//     LinkList* list=(LinkList*)malloc(sizeof(LinkList));
//     list->head=(LinkNode*)malloc(sizeof(LinkNode));
//     list->head->next=NULL;
//     return list;
// }
//
// // 插入节点到链表尾部
// void LinkInsert(LinkList* list,ElemType data) {
//     LinkNode* newNode=(LinkNode*)malloc(sizeof(LinkNode));
//     if(newNode==NULL) {
//         perror("malloc");
//     }
//     newNode->data=data;
//     newNode->next=NULL;
//     LinkNode* current=list->head;
//     while (current->next!=NULL) {
//         current=current->next;
//     }
//     current->next=newNode;
// }
// //头插法
// void LinkHeadInsert(LinkList* list,ElemType data) {
//     LinkNode* newNode=malloc(sizeof(LinkNode));
//     if(newNode==NULL) {
//         perror("malloc");
//     }
//     newNode->data=data;
//     newNode->next=list->head->next;
//     list->head->next=newNode;
// }
//
// //打印链表
// void printLinkList(LinkList* list) {
//     LinkNode* current=list->head->next;
//     while(current!=NULL) {
//         printf("%d ",current->data);
//         current=current->next;
//     }
//     printf("\n");
// }
//
//
// int Remove(LinkList* L,ElemType k,ElemType* x) {
//     assert(L->head);
//     LinkNode* p=L->head->next;
//     LinkNode* q=L->head->next;
//     for (int i=0;i<k;i++) {
//         if(p==NULL) {
//             return 0;
//         }
//         p=p->next;
//     }
//     while (p!=NULL) {
//         p=p->next;
//         q=q->next;
//     }
//
//     *x=q->data;
//     return 1;
// }
//
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     LinkList* L=LinkInit();
//     int x;
//     LinkInsert(L,2);
//     LinkInsert(L,3);
//     LinkInsert(L,9);
//     LinkInsert(L,4);
//     LinkInsert(L,7);
//     LinkInsert(L,9);
//     LinkInsert(L,8);
//     int k=5;
//     int n=Remove(L,k,&x);
//     if(n>0) {
//         printf("倒数第%d个元素值为：%d\n",k,x);
//     }
//     free(L->head);
//     free(L);
//     L=NULL;
//     return 0;
// }
// // （1）【算法思想】
// // 定义指针 p 和 q，初始化指针时均指向单链表的首元结点。首先将 p 沿链表移动到第 k 个结点，而 q 指针保持不变，
// // 这样当 p 移动到第 k+1 个结点时，p 和 q 所指结点的间隔距离为 k。然后 p 和 q 同时向下移动，当 p 为 NULL 时，q 所指向的结点就是该链表倒数第 k 个结点。
// // （2）【算法步骤】
// // ①设定计数器 i = 0，用指针 p 和 q 指向首元结点
// // ②从首元结点开始依顺着链表 link 依次向下遍历链表，
// // 若 p 为 NULL，则转向步骤⑤。
// // ③若 i 小于 k，则 i+1；否则，q 指向下一个结点。
// // ④p 指向下一个结点，转步骤②。
// // ⑤若 i == k，则查找成功，输出该结点的 data 域的值，返回 1；否则，查找失败，返回 0.
